Abstract: Tourists become increasingly dependent on mobile city guides to locate tourist services and retrieve information about nearby points ofinterest (POIs) when visiting unknown destinations. Although several city guides support the provision of personalized tour recommendations to assist tourists visiting the most interesting attractions, existing tour planners only consider walking tours. Herein, we introduce eCOMPASS, a context-aware mobile application which also considers the option of using public transit for moving around. Far beyond than just providing navigational aid, eCOMPASS incorporates multimodality (i.e. time dependency) within its routing logic aiming at deriving nearoptimal sequencing of POIs along recommended tours so as to best utilize time available for sightseeing and minimize waiting time at transit stops. Further advancing the state of the art, eCOMPASS allows users to define arbitrary start/end locations(e.g. the current location of a mobile user) rather than choosing among a fixed set of locations. This paper describes the routing algorithm which comprises the core functionality of eCOMPASS
and discusses the implementation details of the mobile application using the metropolitan area of Berlin (Germany) as case study
Abstract: Smart Dust is a set of a vast number of ultra-small fully
autonomous computing and communication devices, with very
restricted energy and computing capabilities, that co-operate to
quickly and efficiently accomplish a large sensing task. Smart
Dust can be very useful in practice i.e. in the local detection of
a remote crucial event and the propagation of data reporting its
realization. In this work we continue (see [POMC02]) our
effort towards the research on smart dust from a basic algorithmic
pointof view. Under a simple but realistic model for smart dust
we present an interesting problem, which is how to propagate
efficiently information on an event detected locally. Then we
present a new smart dust protocol, which we call the
``Sleep-Awake" protocol, for information propagation that explicitly uses the energy saving features (i.e. the alteration of sleeping and awake time periods) of the smart dust particles. By using both probabilistic some first analysis and extensive
experiments, we provide some first concrete results for the
success probability and the time and energy efficiency of the
protocol, in terms of parameters of the smart dust network. We
note that the study of the interplay of these parameters allows us
to program the smart dust network characteristics accordingly.
Abstract: Smart Dust is a set of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to quickly and efficiently accomplish a large sensing task. Smart Dust can be very useful in practice, i.e., in the local detection of a remote crucial event and the propagation of data reporting its realization. In this work we make an effort towards the research on smart dust from an algorithmic pointof view. We first provide a simple but realistic model for smart dust and present an interesting problem, which is how to propagate efficiently information on an event detected locally. Then we present various smart dust protocols for local detection and propagation that are simple enough to be implemented on real smart dust systems, and perform, under some simplifying assumptions, a rigorous average case analysis of their efficiency and energy consumption (and their interplay). This analysis leads to concrete results showing that our protocols are very efficient and robust. We also validate the analytical results by extensive experiments.
Abstract: The Time Dependent Team Orienteering Problem with Time Windows (TDTOPTW) can be used to model several real life problems. Among them, the route planning problem for tourists interested in visiting multiple points ofinterest (POIs) using public transport. The main objective of this problem is to select POIs that match tourist preferences, while taking into account a multitude of parameters and constraints and respecting the time available for sightseeing in a daily basis. TDTOPTW is NP-hard while almost the whole body of the related literature addresses the non time dependent version of the problem. The only TDTOPTW heuristic proposed so far is based on the assumption of periodic service schedules. Herein, we propose two efficient cluster-based heuristics for the TDTOPTW which yield high quality solutions, take into account time dependency in calculating travel times between POIs and make no assumption on periodic service schedules. The validation scenario for our prototyped algorithms included the metropolitan transit network and real POI sets compiled from Athens (Greece).
Abstract: We present a new finger search tree with
O(
log log
d)
expected search time
in the Random Access Machine (RAM) model of computation for a large class of
input distributions. The parameter
d
represents the number of elements (distance) be-
tween the search element and an element pointed to by a finger, in a finger search tree
that stores
n
elements. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected
O(
log log
n)
search time by incorporating the
distance
d
into the search time complexity, and thus removing the dependence on
n
.
We are also able to show that the search time is
O(
log log
d
+
φ(n))
with high prob-
ability, where
φ(n)
is
any
slowly growing function of
n
. For the need of the analysis
we model the updates by a “balls and bins” combinatorial game that is interesting in
its own right as it involves insertions and deletions of balls according to an unknown
distribution.
Abstract: We present a new finger search tree with O(1) worst-case
update time and O(log log d) expected search time with high probability
in the Random Access Machine (RAM) model of computation for a large
class of input distributions. The parameter d represents the number of
elements (distance) between the search element and an element pointed
to by a finger, in a finger search tree that stores n elements. For the need
of the analysis we model the updates by a "balls and bins" combinatorial
game that is interesting in its own right as it involves insertions and
deletions of balls according to an unknown distribution.
Abstract: We present a new finger search tree with O(log log d) expected search time in the Random
Access Machine (RAM) model of computation for a large class of input distributions. The
parameter d represents the number of elements (distance) between the search element and an
element pointed to by a finger, in a finger search tree that stores n elements. Our data structure
improves upon a previous result by Andersson and Mattsson that exhibits expected O(log log n)
search time by incorporating the distance d into the search time complexity, and thus removing
the dependence on n. We are also able to show that the search time is O(log log d + φ(n)) with
high probability, where φ(n) is any slowly growing function of n. For the need of the analysis
we model the updates by a “balls and bins” combinatorial game that is interesting in its own
right as it involves insertions and deletions of balls according to an unknown distribution.
Abstract: In this paper we examine the problem of searching for some information item in the nodes of a fully
interconnected computer network, where each node contains information relevant to some topic
as well as links to other network nodes that also contain information, not necessarily related to
locally kept information. These links are used to facilitate the Internet users and mobile software
agents that try to locate specific pieces of information. However, the links do not necessarily point
to nodes containing information ofinterest to the user or relevant to the aims of the mobile agent.
Thus an element of uncertainty is introduced. For example, when an Internet user or some search
agent lands on a particular network node, they see a set of links that point to information that is,
supposedly, relevant to the current search. Therefore, we can assume that a link points to relevant
information with some unknown probability p that, in general, is related to the number of nodes
in the network (intuitively, as the network grows, this probability tends to zero since adding more
nodes to the network renders some extant links less accurate or obsolete). Consequently, since there
is uncertainty as to whether the links contained in a node?s Web page are correct or not, a search
algorithm cannot rely on following the links systematically since it may end up spending too much
time visiting nodes that contain irrelevant information. In this work, we will describe and analyze
a search algorithm that is only allowed to transfer a fixed amount of memory along communication
links as it visits the network nodes. The algorithm is, however, allowed to use one bit of memory at
each node as an ?already visited? flag. In this way the algorithm has its memory distributed to the
network nodes, avoiding overloading the network links as it moves from node to node searching for
the information. We work on fully interconnected networks for simplicity reasons and, moreover,
because according to some recent experimental evidence, such networks can be considered to be a
good approximation of the current structure of the World Wide Web.
Abstract: The promises inherent in users coming together to form data
sharing network communities, bring to the foreground new problems formulated
over such dynamic, ever growing, computing, storage, and networking
infrastructures. A key open challenge is to harness these highly
distributed resources toward the development of an ultra scalable, efficient
search engine. From a technical viewpoint, any acceptable solution
must fully exploit all available resources dictating the removal of any
centralized points of control, which can also readily lead to performance
bottlenecks and reliability/availability problems. Equally importantly,
however, a highly distributed solution can also facilitate pluralism in informing
users about internet content, which is crucial in order to preclude
the formation of information-resource monopolies and the biased visibility
of content from economically-powerful sources. To meet these challenges,
the work described here puts forward MINERVA{\^a}{\"i}¿½{\"i}¿½, a novel search
engine architecture, designed for scalability and efficiency. MINERVA{\^a}{\"i}¿½{\"i}¿½
encompasses a suite of novel algorithms, including algorithms for creating
data networks ofinterest, placing data on network nodes, load balancing,
top-k algorithms for retrieving data at query time, and replication algorithms
for expediting top-k query processing. We have implemented the
proposed architecture and we report on our extensive experiments with
real-world, web-crawled, and synthetic data and queries, showcasing the
scalability and efficiency traits of MINERVA{\^a}{\"i}¿½{\"i}¿½.
Abstract: The concept of trust plays an important role in the operation and public acceptance of today's computing environment. Although it is a difficult concept to formalize and handle, many efforts have been made towards a clear definition of trust and the development of systematic ways for trust management. Our central viewpoint is that trust cannot be defined, anymore, as consisting of a static set of rules that define systems properties that hold eternally due to the highly dynamic nature of today's computing systems (e.g. wireless networks, ad-hoc networks, virtual communities and digital territories etc.). Our approach is an effort to define trust in terms of properties that hold with some limiting probability as the the system grows and try to establish conditions that ensure that ??good?? properties hold almost certainly. Based on this viewpoint, in this paper we provide a new framework for defining trust through formally definable properties that hold, almost certainly, in the limit in randomly growing combinatorial structures that model ??boundless?? computing systems (e.g. ad-hoc networks), drawing on results that establish the threshold behavior of predicates written in the first and second order logic. We will also see that, interestingly, some trust models have properties that do not have limiting probabilities. This fact can be used to demonstrate that as certain trust networks grow indefinitely, their trust properties are not certain to be present
Abstract: We consider in this paper the problem of scheduling a set of independent
parallel tasks (jobs) with respect to two criteria, namely,
the makespan (time of the last finishing job) and the minsum (average
completion time). There exist several algorithms with a good
performance guaranty for one of these criteria. We are interested
here in studying the optimization of both criteria simultaneously.
The numerical values are given for the moldable task model, where
the execution time of a task depends on the number of processors
alloted to it. The main result of this paper is to derive explicitly
a family of algorithms guaranteed for both the minsum and the
makespan. The performance guaranty of these algorithms is better
than the best algorithms known so far. The Guaranty curve
of the family is the set of all points (x; y) such that there is an
algorithm with guarantees x on makespan and y on the minsum.
When the ratio on the minsum increases, the curve tends to the
best ratio known for the makespan for moldable tasks (3=2). One
extremal pointof the curves is a (3;6)-approximation algorithm.
Finally a randomized version is given, which improves this results
to (3;4.08).
Abstract: This research attempts a first step towards investigating the aspect of radiation awareness in environments with abundant heterogeneous wireless networking. We call radiation at a pointof a 3D wireless network the total amount of electromagnetic quantity the point is exposed to, our definition incorporates the effect of topology as well as the time domain, data traffic and environment aspects. Even if the impact of radiation to human health remains largely unexplored and controversial, we believe it is worth trying to understand and control. We first analyze radiation in well known topologies (random and grids), randomness is meant to capture not only node placement but also uncertainty of the wireless propagation model. This initial understanding of how radiation adds (over space and time) can be useful in network design, to reduce health risks. We then focus on the minimum radiation path problem of finding the lowest radiation trajectory of a person moving from a source to a destination pointof the network region. We propose three heuristics which provide low radiation paths while keeping path length low, one heuristic gets in fact quite close to the offline solution we compute by a shortest path algorithm. Finally, we investigate the interesting impact on the heuristics' performance of diverse node mobility.
Abstract: In the last few years there has been a great amount ofinterest in Random Constraint Satisfaction
Problems, both from an experimental and a theoretical pointof view. Quite intriguingly, experimental results
with various models for generating random CSP instances suggest that the probability of such problems having
a solution exhibits a ?threshold-like? behavior. In this spirit, some preliminary theoretical work has been done
in analyzing these models asymptotically, i.e., as the number of variables grows. In this paper we prove that,
contrary to beliefs based on experimental evidence, the models commonly used for generating random CSP
instances do not have an asymptotic threshold. In particular, we prove that asymptotically almost all instances
they generate are overconstrained, suffering from trivial, local inconsistencies. To complement this result we
present an alternative, single-parameter model for generating random CSP instances and prove that, unlike
current models, it exhibits non-trivial asymptotic behavior. Moreover, for this new model we derive explicit
bounds for the narrow region within which the probability of having a solution changes dramatically
Abstract: Smart Dust is a set of a ast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that cooperate to quickly and efficiently accomplish a large sensing task. Smart Dust can be very useful in practice i.e. in the local detection of a remote crucial event and the propagation of data reporting its realization. In this work we make an effort towards the research on smart dust from a basic algorithmic pointof view. We first provide a simple but realistic model for smart dust and present an interesting problem, which is how to propagate efficiently information on an event detected locally. Then we present smart dust protocols for local detection and propagation that are simple enough to be implemented on real smart dust systems, and perform, under some simplifying assumptions, a rigorous average case analysis of their efficiency and energy consumption (and their interplay). This analysis leads to concrete results showing that our protocols are very efficient.
Abstract: Smart Dust is a set of a vast number of ultra-small fully
autonomous computing and communication devices, with very restricted
energy and computing capabilities, that co-operate to quickly and efficiently
accomplish a large sensing task.
Smart Dust can be very useful in practice
i.e. in the local detection of a remote crucial event and
the propagation of data reporting its realization.
In this work we make an effort towards the research on smart dust
from a basic algorithmic pointof view.
We first provide a simple but realistic model for smart dust
and present an interesting problem, which is how to propagate efficiently
information on an event detected locally.
Then we present smart dust protocols for local detection
and propagation that are simple enough to be implemented
on real smart dust systems, and perform, under some simplifying assumptions,
a rigorous average case analysis of their efficiency and energy consumption
(and their interplay).
This analysis leads to concrete results showing that our protocols
are very efficient.
Abstract: In emerging pervasive scenarios, data is collected by sensing devices in streams that occur at several distributed points of observation. The size of the data typically far exceeds the storage and computational capabilities of the tiny devices that have to collect and process them. A general and challenging task is to allow (some of) the nodes of a pervasive network to collectively perform monitoring of a neighbourhood ofinterest by issuing continuous aggregate queries on the streams observed in its vicinity. This class of algorithms is fully decentralized and diffusive in nature: collecting all the data at a few central nodes of the network is unfeasible in networks of low capability devices or in the presence of massive data sets. Two main problems arise in this scenario: (i) the intrinsic complexity of maintaining statistics over a data stream whose size greatly exceeds the capabilities of the device that performs the computation; (ii) composing the partial outcomes computed at different points of observation into an accurate, global statistic over a neighbourhood ofinterest, which entails coping with several problems, last but not least the receipt of duplicate information along multiple paths of diffusion.
Streaming techniques have emerged as powerful tools to achieve the general goals described above, in the first place because they assume a computational model in which computational and storage resources are assumed to be far exceeded by the amount of data on which computation occurs. In this contribution, we review the main streaming techniques and provide a classification of the computational problems and the applications they effectively address, with an emphasis on decentralized scenarios, which are of particular interest in pervasive networks